package program.test.stack;

import java.util.*;

/**
 * Leetcode 20号问题:ValidParentheses
 *  题目: 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 *     左括号必须用相同类型的右括号闭合。
 *     左括号必须以正确的顺序闭合。
 *
 * 注意空字符串可被认为是有效字符串。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 */
public class LeetCode20_ValidParentheses {

    private static Map<String, String> flagMap = new HashMap<>();
    private static Set<String> leftFlagGroup = new HashSet<>();
    private static Set<String> rightFlagGroup = new HashSet<>();
    static {
        flagMap.put(")", "(");
        flagMap.put("}", "{");
        flagMap.put("]", "[");

        leftFlagGroup.add("(");
        leftFlagGroup.add("{");
        leftFlagGroup.add("[");

        rightFlagGroup.add(")");
        rightFlagGroup.add("}");
        rightFlagGroup.add("]");
    }

    public static void main(String[] args) {
        String validStr = "{[]}";
        System.out.println(isValid(validStr));
    }

    private static boolean isValid(String s) {
        if (Objects.isNull(s)) {
            return false;
        }

        String newStr = s.trim();
        if ("".equals(newStr)) {
            return true;
        }

        String[] flagGroup = newStr.split("");
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < flagGroup.length; i++) {
            if (leftFlagGroup.contains(flagGroup[i])) {
                // 左侧的符号
                stack.push(flagGroup[i]);
            } else {
                // 右侧的符号
                if (stack.empty()) {
                    return false;
                }

                String peek = stack.peek();
                String leftFlag = flagMap.get(flagGroup[i]);
                if (peek.equals(leftFlag)) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }

        if (stack.isEmpty()) {
            return true;
        }

        return false;
    }

    // luyubobo 老师代码.
    private static boolean isValid2(String str) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }

                char pop = stack.pop();
                if (c == ')' && pop != '(') {
                    return false;
                } else if (c == '}' && pop != '{') {
                    return false;
                } else if (c == ']' && pop != '[') {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}
